public class test08 {
    class Solution {
        List<List<String>> res;
        List<String> list;
        public List<List<String>> solveNQueens(int n) {
            res = new ArrayList<>();
            list = new ArrayList<>();
            char[][] checkboard = new char[n][n];
            //Arrays.fill(checkboard,'.');
            for(char[] c:checkboard){
                Arrays.fill(c,'.');
            }
            backTracking(checkboard,n,0);
            return res;
        }
        private void backTracking(char[][] checkboard,int n,int row){
            if(row==n){
                res.add(Array2List(checkboard));
                return;
            }
            for(int col = 0;col<n;col++){
                if(isValid(checkboard,row,col,n)){
                    checkboard[row][col] = 'Q';
                    backTracking(checkboard,n,row+1);
                    checkboard[row][col] = '.';
                }
            }
        }
        private List<String> Array2List(char[][] checkboard){
            List<String> ans = new ArrayList<>();
            for(char[] c:checkboard){
                ans.add(String.copyValueOf(c));
            }
            return ans;
        }
        private boolean isValid(char[][] checkboard,int row,int col,int n){
            //检查列:列不变，行变
            for(int i = 0;i<n;i++){
                if(checkboard[i][col]=='Q'){
                    return false;
                }
            }
            //检查右上
            for(int i = row-1,j = col+1;i>=0 && j<n;i--,j++){
                if(checkboard[i][j]=='Q'){
                    return false;
                }
            }
            for(int i=row-1,j=col-1;i>=0 && j>=0;i--,j--){
                if(checkboard[i][j]=='Q'){
                    return false;
                }
            }
            return true;
        }
    }
}
